package problem31;

//31.下一个排列
//https://leetcode.cn/problems/next-permutation/?envType=study-plan-v2&envId=top-100-liked

class Solution {
    public void nextPermutation(int[] nums) {
        int n = nums.length;
        int i = n - 2;
        while (i >= 0 && nums[i] >= nums[i+1]) {
            i--;
        }
        // [i+1, n) 为降序
        if (i >= 0) {
            int j = n - 1;
            while (j >= 0) {
                if (nums[j] > nums[i])
                    break;
                j--;
            }
            swap(nums, i, j);
        }
        reserve(nums, i + 1);
    }

    private void swap(int[] nums, int a, int b) {
        int t = nums[a];
        nums[a] = nums[b];
        nums[b] = t;
    }

    private void reserve(int[] nums, int start) {
        int i = start, j = nums.length - 1;
        while (i < j) {
            swap(nums, i++, j--);
        }
    }
}

/*
 * 
 * 123
 * 132
 * 213
 * 231
 * 321
 * 
 * 
 * 
 */